The Fast Fourier Transform (FFT) is the generic name for a class of computationally efficient algorithms that implement the Discrete Fourier Transform (DFT). Until the advent of integrated circuit (IC) devices, the FFT could not be computed fast enough to be of use in the field of real time digital signal processing. Even now, faster and better FFT IC devices are still being pursued by many.
The FFT algorithm has been implemented in integrated circuits that reside on one or more physical devices to process signals in real time or near real time. For example, PDSP16510 manufactured by Plessey is implemented with one chip, and DASP manufactured by Honeywell is implemented with a two-chip set. Although the increased number of chips increases the parallelism in the computation and therefore the speed, disadvantages arise from the multiple-chip implementation.
Most system related failures are related to interconnection failures, including the interconnection between integrated circuit devices and the connection points between an integrated circuit device and the circuit board it resides on. Therefore the multiple-chip implementation inherently increases the possibility of interconnection failures.
Even though computation speed is dramatically improved by the use of more than one chip, the speed is still compromised because of the increased time it takes to transmit signals off-chip. Greater speeds could be realized if all circuits were contained within the space of one integrated circuit device. Therefore, a need has arisen for FFT architecture which provides for a fast FFT circuit. It is further desirable that the FFT architecture permit an FFT circuit implementation on one IC device.
The FFT algorithm is based on the decomposition of the DFT computation. There are two decomposition approaches: decimation-in-time (DIT) and decimation-in-frequency (DIF). The present FFT pipelined architecture is a fully parallel realization of the DIF radix-4 FFT butterfly computation. The pipelined architecture computes the FFT in the most time efficient manner and yields an exceptionally high throughput performance. Furthermore, a 1024-point 16-bit complex FFT circuit constructed in accordance with the present invention can presently be advantageously accommodated on a single chip having a 480 mils.times.480 mils die size.
The present invention provides for an FFT architecture and is directed to overcoming one or more of the problems as set forth above.